#include <iostream>
#include <utility>
#include <memory>

using namespace std;

template<class K, class V>
struct BinaryNode
{
    pair<K, V> m_element;
    BinaryNode * m_left;
    BinaryNode * m_right;

    BinaryNode(){
        m_element = make_pair(0,0);
        m_left = nullptr;
        m_right = nullptr;
    }

    BinaryNode(const pair<K,V> & thePair,
               BinaryNode* theLeft=nullptr,
               BinaryNode* theRight=nullptr){
        m_element = thePair;
        m_left = theLeft;
        m_right = theRight;
    }
};

template<class T, class E>
class BinarySearchTree
{
public:
    using Node = BinaryNode<T,E>;
    virtual ~BinarySearchTree(){};
    virtual pair<T, E>* find(const T& theKey) const = 0;
    virtual void insert(const pair<T,E>& thePair) = 0;
    virtual void erase(const T& theKey) = 0;
    virtual void ascend(ostream & os) const = 0;
    virtual void outputPreOrder(ostream & os) const =0;
};

template <class T, class E>
class LinkedBinarySearchTree : public BinarySearchTree<T,E>
{
public:
    using Node = BinaryNode<T,E>;

    LinkedBinarySearchTree():m_root(nullptr),m_size(0){}

    ~LinkedBinarySearchTree()
    {
        clear(m_root);
        m_size = 0;
    }

    pair<T,E>* find(const T& theKey)const
    {
        Node* p = m_root;
        while(p!= nullptr){
            if(p->m_element.first > theKey){
                p = p->m_left;
            }
            else if(p->m_element.first < theKey){
                p = p->m_right;
            }else{
                return &(p->m_element);
            }
        }

        // 无匹配项
        return nullptr;
    }

    void insert(const pair<T,E>& thePair)
    {
        Node* p = m_root;
        Node* pp = nullptr;
        while (p != nullptr) {
            pp = p;
            if(p->m_element.first > thePair.first){
                p = p->m_left;
            }else if(p->m_element.first < thePair.first){
                p = p->m_right;
            }else{
                // 关键词已经存在的时候，替换内容
                p->m_element.second = thePair.second;
                return ;
            }
        }

        // 插入新的元素
        if(pp == nullptr){
            // 空数
            m_root = new Node(thePair);
        }else{
            if(pp->m_element.first > thePair.first){
                pp->m_left = new Node(thePair);
            }else{
                pp->m_right = new Node(thePair);
            }
        }
        m_size++;
    }

    void erase(const T& theKey)
    {
        Node* p = m_root;
        Node* pp = nullptr;

        while(p!=nullptr && p->m_element.first != theKey){
            pp = p;
            if(theKey < p->m_element.first)
                p = p->m_left;
            else
                p = p->m_right;
        }
        if(p == nullptr)
            return ; // 没有匹配的 Key

        // 当 p 又两个孩子的时候
        if(p->m_left != nullptr && p->m_right != nullptr){
            //在左树中寻找最大的节点
            Node* s = p->m_left;
            Node* ps = p;
            while(s->m_right != nullptr){
                ps = s;
                s = s->m_right;
            }

            // 将左树最大的元素替换 p 的元素
            Node* q = new Node(s->m_element, p->m_left, p->m_right);
            if(pp == nullptr){
                m_root = q;
            }
            else if(p == pp->m_left){
                pp->m_left = q;
            }
            else if(p == pp->m_right){
                pp->m_right = q;
            }

            // 删除 p，并更新 pp 和 p 的指向对象
            if(ps == p) pp = q;
            else pp = ps;
            delete p;
            p = s;
        }

        // 当 p 最多只有一个孩子的时候, c 只能为其中的一棵树或者null
        Node* c;
        if(p->m_left != nullptr)
            c = p->m_left;
        else
            c = p->m_right;

        // 删除 p
        if(p == m_root)
            m_root = c;
        else{
            if(p == pp->m_left)
                pp->m_left = c;
            else
                pp->m_right = c;
        }
        delete p;
        m_size--;
    }

    void ascend(ostream & os) const
    {
        Node * p = m_root;
        inorder_output(p, os);
    }

    void outputPreOrder(ostream& os)const
    {
        Node * p = m_root;
        preorder_output(p, os);
    }

    int getHeight()const
    {
        Node* p = m_root;
        return getHeight(p);
    }

private:

    int getHeight(Node* node)const
    {
        if(node == nullptr) return 0;
        int l = getHeight(node->m_left);
        int r = getHeight(node->m_right);
        return max(l, r) + 1;
    }

    void inorder_output(Node* node,ostream& os) const
    {
        if(node != nullptr) {
            inorder_output(node->m_left, os);
            os<< node->m_element.second<<std::endl;
            inorder_output(node->m_right, os);
        }
    }

    void preorder_output(Node* node,ostream& os) const
    {
        if(node != nullptr) {
            os<< node->m_element.second<<std::endl;
            preorder_output(node->m_left, os);
            preorder_output(node->m_right, os);
        }
    }

    void clear(Node* node)
    {
        if(node != nullptr){
            clear(node->m_left);
            delete node;
            clear(node->m_right);
        }
    }

    Node* m_root;
    int m_size;
};


int main(int argc, char *argv[])
{
    unique_ptr<LinkedBinarySearchTree<int, int>> BSTree(
                new LinkedBinarySearchTree<int, int>());

    std::cout<< " Test for insert"<<std::endl;
    BSTree->insert({4,4});
    BSTree->insert({12,12});
    BSTree->insert({8,8});
    BSTree->insert({16,16});
    BSTree->insert({6,6});
    BSTree->insert({18,18});
    BSTree->insert({24,24});
    BSTree->insert({2,2});
    BSTree->insert({14,14});
    BSTree->insert({3,3});

//    BSTree->ascend(std::cout);
    BSTree->outputPreOrder(std::cout);
    std::cout<<"The height is:"<<BSTree->getHeight()<<std::endl;
//    std::cout<<" Test for erase"<<std::endl;
//    BSTree->erase(12);
//    BSTree->erase(14);
//    BSTree->ascend(std::cout);

    return 0;
}





